#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode() {
	link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link) {
	this->dest = dest;
	this->link = link;
}



int EdgeNode::getDest() {
	return dest;
}

EdgeNode* EdgeNode::getNext() {
	return link;
}

void EdgeNode::setDest(int dest) {
	this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link) {
	this->link = link;
}

VertexNode::VertexNode() {

}

VertexNode::VertexNode(char data, EdgeNode* firstEdge) {
	this->data = data;
	this->firstEdge = firstEdge;
}

VertexNode::~VertexNode() {

}

char VertexNode::getData() {
	return data;
}

EdgeNode* VertexNode::getFirstEdge() {
	return firstEdge;
}

void VertexNode::setData(char data) {
	this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge) {
	this->firstEdge = firstEdge;
}

MyGraph::MyGraph() {
	nodeNum = 0;
	edgeNum = 0;
	VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList) {
	this->nodeNum = nodeNum;
	this->edgeNum = edgeNum;
	VexList = new VertexNode[nodeNum];
	for (int i = 0; i < nodeNum; i++)
	{
		VexList[i].setData(nodeList[i]);
		VexList[i].setFirstEdge(NULL);
	}
	EdgeNode* p;
	for (int i = 0; i < edgeNum; i++)
	{
		p = new EdgeNode;
		int head, tail;
		head = edgeStartList[i];
		tail = edgeEndList[i];

		p->setDest(head);
		p->setNext(VexList[tail].getFirstEdge());
		VexList[tail].setFirstEdge(p);

		p = new EdgeNode;
		p->setDest(tail);
		p->setNext(VexList[head].getFirstEdge());
		VexList[head].setFirstEdge(p);
	}
}

MyGraph::~MyGraph() {

}

int MyGraph::getNodeNum() {
	return this->nodeNum;
}

int MyGraph::getEdgeNum() {
	return this->edgeNum;
}

string MyGraph::printGraph() {
	string s = "";
	for (int i = 0; i < getNodeNum(); i++)
	{
		s += (char)VexList[i].getData();
		s += ':';
		EdgeNode* p;
		p = VexList[i].getFirstEdge();
		while (p != NULL)
		{
			s += " ";
			s += (char)VexList[p->getDest()].getData();
			p = p->getNext();
		}
		if (i != getNodeNum() - 1)
		{
			s += '\n';
		}
	}
	return s;
}



void MyGraph::DFS(int v, int* visited, string& result) {
	result += (char)VexList[v].getData();
	result += " ";
	EdgeNode* p;
	p = VexList[v].getFirstEdge();
	while (p != NULL)
	{
		if (visited[p->getDest()] == 0)
		{
			visited[p->getDest()] = 1;
			DFS(p->getDest(), visited, result);
		}
		p = p->getNext();
	}
}

string MyGraph::graph_DFS_Traverse() {
	string result = "";
	visited = new int[getNodeNum()];
	for (int i = 0; i < getNodeNum(); i++)
	{
		visited[i] = 0;
	}
	visited[0] = 1;
	DFS(0, visited, result);
	return result;
}

void MyGraph::BFS(int v, int* visited, string& result) {
	queue<VertexNode>que;
	que.push(VexList[0]);
	visited[0] = 1;
	while (!que.empty())
	{
		VertexNode t = que.front();
		que.pop();
		result += (char)t.getData();
		result += " ";
		EdgeNode* p = t.getFirstEdge();
		while (p != NULL)
		{
			if (visited[p->getDest()] == 0)
			{
				que.push(VexList[p->getDest()]);
				visited[p->getDest()] = 1;
			}
			p = p->getNext();
		}
	}
}

string MyGraph::graph_BFS_Traverse() {
	string result = "";
	visited = new int[getNodeNum()];
	for (int i = 0; i < getNodeNum(); i++)
	{
		visited[i] = 0;
	}
	BFS(0, visited, result);
	return result;
}

//int main() 
//{ 
//	int nodeNum = 9; 
//	int edgeNum = 10; 
//	char nodeList[9] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I' }; 
//	int edgeStartList[10] = { 0, 0, 0, 1, 1, 4, 2, 3, 5, 7 }; 
//	int edgeEndList[10] = { 1, 2, 3, 2, 4, 6, 5, 5, 7, 8 }; 
//	MyGraph g(nodeNum, edgeNum, nodeList, edgeStartList, edgeEndList); 
//
//	cout << g.printGraph() << endl; 
//	cout << g.graph_DFS_Traverse() << endl; 
//	cout << g.graph_BFS_Traverse() << endl; 
//	return 0; 
//}